\batchmode
\makeatletter
\def\input@path{{/Users/sergei.winitzki/Code/talks/ftt-fp/}}
\makeatother
\documentclass[english]{beamer}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{babel}
\usepackage{amsmath}
\usepackage[all]{xy}
\ifx\hypersetup\undefined
  \AtBeginDocument{%
    \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
  }
\else
  \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
\fi

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
% this default might be overridden by plain title style
\newcommand\makebeamertitle{\frame{\maketitle}}%
% (ERT) argument for the TOC
\AtBeginDocument{%
  \let\origtableofcontents=\tableofcontents
  \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
  \def\gobbletableofcontents#1{\origtableofcontents}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme[secheader]{Boadilla}
\usecolortheme{seahorse}
\title[Chapter 9: Traversable functors]{Chapter 9: Traversable functors}
%\subtitle{Part 2: Their laws and structure}
\author{Sergei Winitzki}
\date{2018-09-03}
\institute[ABTB]{Academy by the Bay}
\setbeamertemplate{headline}{} % disable headline at top
\setbeamertemplate{navigation symbols}{} % disable navigation bar at bottom
\usepackage[all]{xy}
\usepackage[nocenter]{qtree}
\makeatletter
% Macros to assist LyX with XYpic when using scaling.
\newcommand{\xyScaleX}[1]{%
\makeatletter
\xydef@\xymatrixcolsep@{#1}
\makeatother
} % end of \xyScaleX
\makeatletter
\newcommand{\xyScaleY}[1]{%
\makeatletter
\xydef@\xymatrixrowsep@{#1}
\makeatother
} % end of \xyScaleY

\makeatother

\begin{document}
\frame{\titlepage}
\begin{frame}{Motivation for the \texttt{\textcolor{blue}{\footnotesize{}traverse}}
operation}
\begin{itemize}
\item Consider data of type $\text{List}^{A}$ and processing $f:A\Rightarrow\text{Future}^{B}$
\item Typically, we want to wait until the entire data set is processed
\item What we need is $\text{List}^{A}\Rightarrow\left(A\Rightarrow\text{Future}^{B}\right)\Rightarrow\text{Future}^{\text{List}^{B}}$
\item Generalize: $L^{A}\Rightarrow\left(A\Rightarrow F^{B}\right)\Rightarrow F^{L^{B}}$
for some type constructors $F$, $L$
\item This operation is called \texttt{\textcolor{blue}{\footnotesize{}traverse}} 
\begin{itemize}
\item How to implement it: for example, a 3-element list is $A\times A\times A$
\item Consider $L^{A}\equiv A\times A\times A$, apply $\text{map}\,f$
and get $F^{B}\times F^{B}\times F^{B}$
\item We will get $F^{L^{B}}\equiv F^{B\times B\times B}$ if we can apply
\texttt{\textcolor{blue}{\footnotesize{}zip}} as $F^{B}\times F^{B}\Rightarrow F^{B\times B}$
\end{itemize}
\item So we need to assume that $F$ is applicative
\item In Scala, we have \texttt{\textcolor{blue}{\footnotesize{}Future.traverse()}}
that assumes $L$ to be a sequence
\begin{itemize}
\item This is the easy-to-remember example that fixes the requirements
\end{itemize}
\item Questions:
\begin{itemize}
\item Which functors $L$ can have this operation?
\item Can we express \texttt{\textcolor{blue}{\footnotesize{}traverse}}
through a simpler operation?
\item What are the required laws for \texttt{\textcolor{blue}{\footnotesize{}traverse}}?
\item What about contrafunctors or profunctors?
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Deriving the \texttt{\textcolor{blue}{\footnotesize{}sequence}} operation}
\begin{itemize}
\item \vspace{-0.1cm}The type signature of \texttt{\textcolor{blue}{\footnotesize{}traverse}}
is a complicated ``lifting''
\begin{itemize}
\item A ``lifting'' is often equivalent to a simpler natural transformation
\end{itemize}
\item To derive it, ask: what is missing from \texttt{\textcolor{blue}{\footnotesize{}fmap}}
to do the job of \texttt{\textcolor{blue}{\footnotesize{}traverse}}?{\footnotesize{}
\[
\text{fmap}_{L}:(A\Rightarrow F^{B})\Rightarrow L^{A}\Rightarrow L^{F^{B}}
\]
}{\footnotesize\par}
\item We need $F^{L^{B}}$, but the \texttt{\textcolor{blue}{\footnotesize{}traverse}}
operation gives us $L^{F^{B}}$ instead
\begin{itemize}
\item What's missing is a natural transformation \texttt{\textcolor{blue}{\footnotesize{}sequence}}
$:L^{F^{B}}\Rightarrow F^{L^{B}}$ 
\end{itemize}
\item The functions \texttt{\textcolor{blue}{\footnotesize{}traverse}} and
\texttt{\textcolor{blue}{\footnotesize{}sequence}} are computationally
equivalent:{\footnotesize{}
\[
\text{trav}\,f^{\underline{A\Rightarrow F^{B}}}=\text{fmap}_{L}\,f\circ\text{seq}
\]
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & L^{F^{B}}\ar[rd]\sp(0.45){\text{seq}}\\
L^{A}\ar[ru]\sp(0.45){\text{fmap}_{L}\,f^{\underline{A\Rightarrow F^{B}}}}\ar[rr]\sb(0.45){\text{trav}\,f^{\underline{A\Rightarrow F^{B}}}} &  & F^{L^{B}}
}
\]
}Here $F$ is an \emph{arbitrary} applicative functor
\begin{itemize}
\item Keep in mind the example \texttt{\textcolor{blue}{\footnotesize{}Future.sequence}}
$:\text{List}^{\text{Future}^{X}}\Rightarrow\text{Future}^{\text{List}^{X}}$
\item Examples: $L^{A}\equiv A\times A\times A$; $L^{A}=\text{List}^{A}$;
finite trees 
\item Non-traversable: $L^{A}\equiv R\Rightarrow A$; lazy list (``infinite
product'')
\begin{itemize}
\item Note: We \emph{cannot have} the opposite transformation $F^{L^{B}}\Rightarrow L^{F^{B}}$
\end{itemize}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Polynomial functors are traversable}
\begin{itemize}
\item \vspace{-0.1cm}Generalize from the example $L^{A}\equiv A\times A\times A$
to other polynomials
\item Polynomial functors have the form {\small{}
\[
L^{A}\equiv Z\times A\times...\times A+Y\times A\times...\times A+...+Q\times A+P
\]
}{\small\par}
\item To implement {\small{}$\text{seq}:L^{F^{B}}\Rightarrow F^{L^{B}}$},
consider monomial {\small{}$L^{A}\equiv Z\times A\times...\times A$}{\small\par}
\item We have $L^{F^{B}}=Z\times F^{B}\times...\times F^{B}$; apply \texttt{\textcolor{blue}{\footnotesize{}zip}}
and get $Z\times F^{B\times...\times B}$ 
\item Lift $Z$ into the functor $F$ using $Z\Rightarrow F^{A}\Rightarrow F^{Z\times A}$
(or with $F.\text{pure}$)
\item The result is $F^{Z\times B\times...\times B}\equiv F^{L^{B}}$
\begin{itemize}
\item For a polynomial $L^{A}$, do this to each monomial, then lift to
$F^{L^{B}}$
\item Note that we could apply \texttt{\textcolor{blue}{\footnotesize{}zip}}
in various different orders
\end{itemize}
\item The traversal order is arbitrary, may be application-specific
\item Non-polynomial functors are not traversable (see \href{http://www.cs.ox.ac.uk/jeremy.gibbons/publications/uitbaf.pdf}{Bird et al., 2013})
\begin{itemize}
\item Example: $L^{A}\equiv E\Rightarrow A$; $F^{A}\equiv1+A$; can't have
{\small{}$\text{seq}:L^{F^{B}}\Rightarrow F^{L^{B}}$}{\small\par}
\end{itemize}
\item All polynomial functors are traversable, and usually in several ways
\begin{itemize}
\item It is still useful to have a type class for traversable functors
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Motivation for the laws of the \texttt{\textcolor{blue}{\footnotesize{}traverse}}
operation }
\begin{itemize}
\item \vspace{-0.2cm}The \href{https://arxiv.org/pdf/1202.2919.pdf}{\textquotedblleft law of traversals\textquotedblright{} paper}
(2012) argues that \texttt{\textcolor{blue}{\footnotesize{}traverse}}
should ``visit each element'' of the container $L^{A}$ exactly
once, and evaluate each corresponding ``effect'' $F^{B}$ exactly
once; then they formulate the laws
\item To derive the laws, use the ``lifting'' intuition for \texttt{\textcolor{blue}{\footnotesize{}traverse}},{\footnotesize{}
\[
\text{trav}:(A\Rightarrow F^{B})\Rightarrow L^{A}\Rightarrow F^{L^{B}}
\]
}{\footnotesize\par}
\end{itemize}
{\footnotesize{}L}ook for ``identity'' and ``composition'' laws:
\begin{enumerate}
\item ``Identity'' as \texttt{\textcolor{blue}{\footnotesize{}pure}} $:A\Rightarrow F^{A}$
must be lifted to \texttt{\textcolor{blue}{\footnotesize{}pure}} $:L^{A}\Rightarrow F^{L^{A}}$
\item ``Identity'' as $\text{id}^{\underline{A\Rightarrow A}}$ with $F^{A}\equiv A$
(identity functor) lifted to $\text{id}^{\underline{L^{A}\Rightarrow L^{A}}}$
\item ``Compose'' $f:A\Rightarrow F^{B}$ and $g:B\Rightarrow G^{C}$
to get $h:A\Rightarrow F^{G^{C}}$, where $F$, $G$ are applicative;
a traversal with $h$ maps $L^{A}$ to $F^{G^{L^{C}}}$ and must be
equal to the composition of traversals with $f$ and then with $g^{F\uparrow}$
\end{enumerate}
Questions:
\begin{itemize}
\item Are the laws for the \texttt{\textcolor{blue}{\footnotesize{}sequence}}
operation simpler?
\item Are all these laws independent?
\item What functors $L$ satisfy these laws \emph{for all} applicative functors
$F$?
\end{itemize}
\end{frame}

\begin{frame}{Formulation of the laws for \texttt{\textcolor{blue}{\footnotesize{}traverse}} }
\begin{itemize}
\item \vspace{-0.15cm}Identity law: For any applicative functor $F$, 
\[
\text{trav}\left(\text{pure}\right)=\text{pure}
\]
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc}\ L^{A}\ar[rr]\sp(0.45){\text{pure}^{\underline{L^{A}\Rightarrow F^{L^{A}}}}}\ar[rr]\sb(0.45){\text{trav}\,(\text{pure}^{\underline{A\Rightarrow F^{A}}})} &  & F^{L^{A}}}
\]

\begin{itemize}
\item Second identity law: $\text{trav}^{\text{Id}}(\text{id}^{A})=\text{id}^{L^{A}}$
is a consequence with $F=\text{Id}$
\begin{itemize}
\item So, we need only one identity law
\end{itemize}
\end{itemize}
\item Composition law: For any $f^{\underline{A\Rightarrow F^{B}}}$ and
$g^{\underline{B\Rightarrow G^{C}}}$, \& applicative $F$ and $G$,
\[
\text{trav}\,f\circ\left(\text{trav}\,g\right)^{F\uparrow}=\text{trav}\,\big(f\circ g^{F\uparrow}\big)
\]
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{L^{B}}\ar[rd]\sp(0.55){\ \ \ \ \text{fmap}_{F}\big(\text{trav}^{G}\,g\big)^{\underline{L^{B}\Rightarrow G^{L^{C}}}}}\\
L^{A}\ar[ru]\sp(0.45){\text{trav}^{F}\,f^{\underline{A\Rightarrow F^{B}}}}\ar[rr]\sb(0.45){\text{trav}^{F^{G}}\,h^{\underline{A\Rightarrow F^{G^{C}}}}} &  & F^{G^{L^{C}}}
}
\]
where $h^{\underline{A\Rightarrow F^{G^{C}}}}\equiv f\circ g^{F\uparrow}$.
(Note: $H^{A}\equiv F^{G^{A}}$ is applicative!)
\end{itemize}
\end{frame}

\begin{frame}{Derivation of the laws for \texttt{\textcolor{blue}{\footnotesize{}sequence}} }

\vspace{-0.15cm}Express $\text{trav}\,f=f^{L\uparrow}\circ\text{seq}$
and substitute into the laws for $\text{trav}$:
\begin{itemize}
\item Identity law:{\small{} $\text{trav}\left(\text{pure}\right)=\text{pure}^{L\uparrow}\circ\text{seq}=\text{pure}$}{\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & L^{F^{A}}\ar[rd]\sp(0.45){\text{seq}}\\
L^{A}\ar[rr]\sb(0.45){\text{pure}^{L^{A}}}\ar[ru]\sp(0.45){\text{fmap}_{L}\,\text{pure}^{A}} &  & F^{L^{A}}
}
\]
}{\footnotesize\par}
\end{itemize}
Naturality law: $\text{seq}\circ g^{F\uparrow L\uparrow}=g^{L\uparrow F\uparrow}\circ\text{seq}$
with $g^{\underline{A\Rightarrow B}}$, mapping $L^{F^{A}}\Rightarrow F^{L^{B}}$
\begin{itemize}
\item Composition law: {\footnotesize{}
\begin{align*}
\text{trav}\,f\circ\left(\text{trav}\,g\right)^{F\uparrow} & =f^{L\uparrow}\circ\text{seq}\circ\left(g^{L\uparrow}\circ seq\right)^{F\uparrow}\\
 & =f^{L\uparrow}\circ\text{seq}\circ g^{L\uparrow F\uparrow}\circ\text{seq}^{F\uparrow}=f^{L\uparrow}\circ g^{F\uparrow L\uparrow}\circ\text{seq}\circ\text{seq}^{F\uparrow}\\
\text{trav}\,\big(f\circ g^{F\uparrow}\big) & =\big(f\circ g^{F\uparrow}\big)^{L\uparrow}\circ\text{seq}=f^{L\uparrow}\circ g^{F\uparrow L\uparrow}\circ\text{seq}
\end{align*}
}Now omit the common prefix $f^{...}\circ g^{...}$ and obtain: $\text{seq}\circ\text{seq}^{F\uparrow}=\text{seq}${\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{L^{G^{A}}}\ar[rd]\sp(0.6){\ (\text{seq}^{G})^{F\uparrow}}\\
L^{F^{G^{A}}}\ar[ru]\sp(0.45){\text{seq}^{F}}\ar[rr]\sb(0.45){\text{seq}^{F^{G^{?}}}} &  & F^{G^{L^{A}}}
}
\]
}{\footnotesize\par}
\end{itemize}
\end{frame}

\begin{frame}{Constructions of traversable and bitraversable functors}

Constructions of traversable functors:
\begin{enumerate}
\item $L^{A}\equiv Z$ (constant functor) and $L^{A}\equiv A$ (identity
functor)
\item $L^{A}\equiv G^{A}\times H^{A}$ for any traversable $G^{A}$ and
$H^{A}$
\item $L^{A}\equiv G^{A}+H^{A}$ for any traversable $G^{A}$ and $H^{A}$
\item $L^{A}\equiv S^{A,L^{A}}$ (recursive) for a bitraversable bifunctor
$S^{A,B}$ 
\begin{itemize}
\item If $L^{A}$ is infinite, laws will appear to hold but \texttt{\textcolor{blue}{\footnotesize{}seq}}
will not terminate
\end{itemize}
A bifunctor $S^{A,B}$ is \textbf{bitraversable} if \texttt{\textcolor{blue}{\footnotesize{}bisequence}}
exists such that
\[
\text{biseq}:S^{F^{A},F^{B}}\Rightarrow F^{S^{A,B}}
\]
 for any applicative functor $F$; the analogous laws must hold
\end{enumerate}
Constructions of bitraversable bifunctors:
\begin{enumerate}
\item $S^{A,B}\equiv Z$, $S^{A,B}\equiv A$, and $S^{A,B}=B$
\item $S^{A,B}\equiv G^{A,B}\times H^{A,B}$ for any bitraversable $G$
and $H$
\item $S^{A,B}\equiv G^{A,B}+H^{A,B}$ for any bitraversable $G$ and $H$
\end{enumerate}
\begin{itemize}
\item All polynomial bifunctors are bitraversable
\item All polynomial functors, including recursive functors, are traversable
\end{itemize}
\end{frame}

\begin{frame}{Foldable functors: traversing with respect to a monoid}
\begin{itemize}
\item \vspace{-0.15cm}Take $F^{A}\equiv Z$ where $Z$ is a monoid
\begin{itemize}
\item The \texttt{\textcolor{blue}{\footnotesize{}zip}} operation is the
monoid operation $\oplus$
\end{itemize}
\item The type signature of \texttt{\textcolor{blue}{\footnotesize{}traverse}}
becomes $\left(A\Rightarrow Z\right)\Rightarrow L^{A}\Rightarrow Z$
\begin{itemize}
\item This method is called \texttt{\textcolor{blue}{\footnotesize{}foldMap}} 
\end{itemize}
\item The type signature of \texttt{\textcolor{blue}{\footnotesize{}seq}}
becomes $L^{Z}\Rightarrow Z$
\begin{itemize}
\item This is called \texttt{\textcolor{blue}{\footnotesize{}mconcat}} --
combines all values in $L^{Z}$ with $Z$'s $\oplus$
\end{itemize}
\item It is convenient to define the \texttt{\textcolor{blue}{\footnotesize{}Foldable}}
type class
\begin{itemize}
\item But it has no laws any more
\item All traversable functors are also foldable
\end{itemize}
\item The \texttt{\textcolor{blue}{\footnotesize{}foldLeft}} method can
be defined via \texttt{\textcolor{blue}{\footnotesize{}foldMap}} with
$Z\equiv(B\Rightarrow B)$:
\[
\text{foldl}:\left(A\Rightarrow B\Rightarrow B\right)\Rightarrow L^{A}\Rightarrow B\Rightarrow B
\]
\end{itemize}
\end{frame}

\begin{frame}{Traversable contrafunctors and profunctors are not useful}

\vspace{-0.15cm}Traversing profunctors with respect to functors $F$:
effects of $F$ are ignored
\begin{itemize}
\item All contrafunctors $C^{A}$ are traversable w.r.t.~applicative profunctors
$F^{A}$,{\footnotesize{}
\[
\text{seq}:C^{F^{A}}\Rightarrow F^{C^{A}}\equiv\text{pure}^{C\downarrow}\circ\text{pure}
\]
\[
\xymatrix{C^{F^{A}}\ar[r]\sp(0.5){\text{cmap}_{C}\text{pure}_{F}^{A}}\xyScaleY{0.2pc}\xyScaleX{3pc} & C^{A}\ar[r]\sp(0.5){\text{pure}_{F}^{C^{A}}} & F^{C^{A}}}
\]
}{\footnotesize\par}
\item But not profunctors that are neither functors not contrafunctors
\item Counterexample: $P^{A}\equiv A\Rightarrow A$; need $\text{seq}:\left(F^{A}\Rightarrow F^{A}\right)\Rightarrow F^{A\Rightarrow A}$;
we can't get an $A\Rightarrow A$, so the only implementation is to
return $\text{pure}_{F}\left(\text{id}\right)$, which ignores its
argument and so will fail the identity law 
\end{itemize}
Traversing profunctors $L$ with respect to profunctors $F$: effects
are ignored
\begin{itemize}
\item Counterexample 1: contrafunctor $L^{A}\equiv A\Rightarrow R$ and
contrafunctor $F^{A}\equiv A\Rightarrow S$, a \texttt{\textcolor{blue}{\footnotesize{}seq}}
of type $L^{F^{A}}\Rightarrow F^{L^{A}}$ must return $1+0$
\item Counterexample 2: contrafunctor $F^{A}\equiv\left(R\Rightarrow A\right)\Rightarrow S$
and functor $L^{A}\equiv1+A$; \texttt{\textcolor{blue}{\footnotesize{}seq}}
must return $1+0$
\item So, the result is trivial and probably not useful
\begin{itemize}
\item Laws of traversables allow ignoring the effects of $F$
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Examples of usage}
\begin{enumerate}
\item \vspace{-0.15cm}Convert foldable data structures to list
\item Fold a tree to aggregate data
\item Decorate a tree with Depth-First traversal order labels
\item Implement \texttt{\textcolor{blue}{\footnotesize{}scanMap}} and \texttt{\textcolor{blue}{\footnotesize{}scanLeft}}
as \texttt{\textcolor{blue}{\footnotesize{}traverse}} with a state
monad
\item Traversal for a non-monadic ``rigid'' tree $T^{A}\equiv A+T^{A\times A}$
\begin{itemize}
\item The corresponding construction is $L^{A}\equiv S^{A,L^{R^{A}}}$ where
$R$ is applicative and traversable and $S$ is bitraversable
\end{itemize}
\end{enumerate}
What \emph{cannot} be implemented as a traversal:
\begin{itemize}
\item Breadth-first traversal for a tree as  \Tree[ [ 2 [ 3 4 ] ] 1 ]  
\item Depth labeling of a tree as  \Tree[ [ 2 [ 3 3 ] ] 1 ] {\footnotesize{} }{\footnotesize\par}
\end{itemize}
\end{frame}
size{} }{\footnotesize\par}
\end{itemize}
\end{frame}

\begin{frame}{Naturality with respect to applicative functor as parameter}
\begin{itemize}
\item \vspace{-0.15cm}The{\footnotesize{} }\texttt{\textcolor{blue}{\footnotesize{}traverse}}
method must be ``generic in the functor $F$'':{\footnotesize{}
\[
\text{trav}^{F,A,B}:(A\Rightarrow F^{B})\Rightarrow L^{A}\Rightarrow F^{L^{B}}
\]
}Which means: The code of \texttt{\textcolor{blue}{\footnotesize{}traverse}}
can only use \texttt{\textcolor{blue}{\footnotesize{}pure}} and \texttt{\textcolor{blue}{\footnotesize{}zip}}
from $F$
\item A functor {\footnotesize{}$F^{A}$ }is ``generic in $A$'': have
{\footnotesize{}$\text{fmap}:\left(A\Rightarrow B\right)\Rightarrow F^{A}\Rightarrow F^{B}$}{\footnotesize\par}
\item ``Generic in $F$'' means mapping {\footnotesize{}$\left(F\Rightarrow G\right)\Rightarrow\text{trav}^{F}\Rightarrow\text{trav}^{G}$}
in some way
\end{itemize}
Mathematical formulation:
\begin{itemize}
\item For any natural transformation $F^{A}\Rightarrow G^{A}$ between applicative
functors $F$ and $G$ such that $F.\text{pure}$ and $F.\text{zip}$
are mapped into $G.\text{pure}$ and $G.\text{zip}$, the result of
transforming $\text{trav}^{F}$ is $\text{trav}^{G}$
\begin{itemize}
\item Such a natural transformation is a morphism of applicative functors
\item Category theory can describe {\footnotesize{}$\left(F\Rightarrow G\right)\Rightarrow\text{trav}^{F}\Rightarrow\text{trav}^{G}$}
as a ``lifting''
\item Use a more general definition of category than what we had so far
(morphisms between type constructors)
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Exercises}
\begin{enumerate}
\item {\footnotesize{}\vspace{-0.15cm}Show that any traversable functor
$L$ admits a method 
\[
\text{consume}:(L^{A}\Rightarrow B)\Rightarrow L^{F^{A}}\Rightarrow F^{B}
\]
for any applicative functor $F$. Show that }\texttt{\textcolor{blue}{\footnotesize{}traverse}}{\footnotesize{}
and }\texttt{\textcolor{blue}{\footnotesize{}consume}}{\footnotesize{}
are equivalent.}{\footnotesize\par}
\item {\footnotesize{}Show that $\text{seq}:L^{F^{A}}\Rightarrow F^{L^{A}}=\text{id}$
if we choose $F^{A}\equiv A$ as the identity functor. }{\footnotesize\par}
\item {\footnotesize{}Show that the identity law is not satisfied by an
implementation of $\text{seq}:L^{F^{A}}\Rightarrow F^{L^{A}}$ for
$F^{A}\equiv1+A$ when $\text{seq}$ always returns an empty option.}{\footnotesize\par}
\item {\footnotesize{}Show that $K^{A}\equiv G^{H^{A}}$ is traversable
if $G$ and $H$ are traversable.}{\footnotesize\par}
\item {\footnotesize{}Show that all the bitraversable laws hold for the
bifunctor $S^{A,B}\equiv A\times B$.}{\footnotesize\par}
\item {\footnotesize{}For the tree-like type defined as $T^{A}\equiv1+A\times T^{A}\times T^{A}$,
define a traversable instance. Verify that the laws hold, using a
suitable bifunctor $S^{X,Y}$.}{\footnotesize\par}
\item {\footnotesize{}For a tree type $T^{A}$ of your choice, implement
a traversable instance for right-to-left traversal order, and test
that the tree is decorated with labels as  \Tree[ [ 4 [ 3 2 ] ] 1 ]  }{\footnotesize\par}
\item {\footnotesize{}Implement a traversable instance for a ``rose tree''
$T^{A}\equiv A+\text{List}^{T^{A}}$. Represent $T^{A}$ via a suitable
bifunctor $S^{X,Y}$ and show that $S$ is bitraversable (use constructions).}{\footnotesize\par}
\item {\footnotesize{}Is the recursive type constructor $L^{A}\equiv A+L^{\text{List}^{A}}$
traversable? Explain what sort of data container it is.}{\footnotesize\par}
\end{enumerate}
\end{frame}

\end{document}
